#include <QuickSortRandom.h>

template<typename T>
inline void swapT(T &t1, T &t2)
{
	T temp;
	temp = t1;
	t1=t2;
	t2=temp;
}

template<typename T>
void _StoogeSort(T *vec, size_t startPos, size_t endPos)
{
// 	if(vec[startPos]>vec[endPos])
// 		swapT(vec[startPos],vec[endPos]);
// 	if(startPos+1>=endPos)
// 		return;
	if(endPos-startPos+1<=1000)
	{
		_QuickSortRandom(vec,startPos,endPos);
		return ;
	}
	size_t k = 0;
	if(endPos>startPos)
		k= (endPos-startPos+1)/3;
	if(k>endPos)
		printf("error\n");
	_StoogeSort(vec,startPos,endPos-k);
	_StoogeSort(vec,startPos+k,endPos);
	_StoogeSort(vec,startPos,endPos-k);
}

template <typename T>
void StoogeSort(T* vec, size_t cnt)
{
	_StoogeSort(vec,0,cnt-1);
}
